#include<bits/stdc++.h>
using namespace std;
const int N = 3015;
const int M = 101;

struct Node{
    int t,val,h;
    Node(){}
    bool operator<(const Node& node)const{
        return t<node.t;
    }
};

int dep,n;
Node nodes[M];
int ans1 = 1e9, ans2 = 10;
unordered_map<int,unordered_map<int,unordered_map<int,bool>>> mp;

void dfs(int t,int h,int idx){
    if(h>=dep){
        ans1 = min(ans1,nodes[idx-1].t);
        return;
    }
    if(idx>n || t<nodes[idx].t){
        ans2 = max(ans2,t);
        return;
    }
    if(mp[t][h][idx]) return;
    mp[t][h][idx] = true;
    dfs(t,h+nodes[idx].h,idx+1);
    dfs(t+nodes[idx].val,h,idx+1);
}


int main(){
    cin>>dep>>n;
    for(int i=1;i<=n;i++){
        cin>>nodes[i].t>>nodes[i].val>>nodes[i].h;
    }
    sort(nodes+1,nodes+n+1);
    dfs(10,0,1);
    if(ans1==1e9) cout<<ans2<<endl;
    else cout<<ans1<<endl;
    return 0;
}